package com.mxw.算法之美.a18动态规划;


public class a03最长公共子串长度 {

    /**
     * 如果 a[i]与 b[j]互相匹配，我们将最大公共子串长度加一，并且继续考察 a[i+1]和 b[j+1]。
     * 如果 a[i]与 b[j]不匹配，最长公共子串长度不变，这个时候，有两个不同的决策路线:
     * 删除 a[i]，或者在 b[j]前面加上一个字符 a[i]，然后继续考察 a[i+1] 和 b[j];
     * 删除 b[j]，或者在 a[i]前面加上一个字符 b[j]，然后继续考察 a[i]和 b[j+1]。
     */

    public int lcs(char[] a, char[] b) {
        int n = a.length;
        int m = b.length;
        int[][] maxlcs = new int[n][m];

        // 初始化第0行：a[0..0] 与 b[0..j] 的最长公共子串长度
        for (int j = 0; j < m; j++) {
            if (a[0] == b[j]) {
                maxlcs[0][j] = 1;
            } else if (j != 0) {
                maxlcs[0][j] = maxlcs[0][j - 1];
            } else {
                maxlcs[0][j] = 0;
            }
        }

        // 初始化第0列：a[0..i] 与 b[0..0] 的最长公共子串长度
        for (int i = 0; i < m; i++) {
            if (a[i] == b[0]) {
                maxlcs[i][0] = 1;
            } else if (i != 0) {
                maxlcs[i][0] = maxlcs[i - 1][0];
            } else {
                maxlcs[i][0] = 0;
            }
        }

        // 填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j]) {
                    maxlcs[i][j] = max(
                            maxlcs[i - 1][j],
                            maxlcs[i][j-1],
                            maxlcs[i-1][j - 1]+1
                    );
                } else {
                    maxlcs[i][j] = max(
                            maxlcs[i - 1][j],
                            maxlcs[i][j-1],
                            maxlcs[i-1][j - 1]
                    );
                }
            }
        }
        return maxlcs[n - 1][m - 1];
    }

    public int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }
}
